// 560. 和为 K 的子数组
//枚举

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count=0;
        for(int start=0;start<nums.size();++start){
            int sum=0;
            for(int end=start;end>=0;end--){
                sum+=nums[end];
                if(sum==k){
                    count++;
                }
            }
        }
        return count;
    }
};

//前缀和+哈希表优化
class Solution{
public:
    int subarrySum(vector<int>&nums, int k){
        unordered_map<int,int>mp;
        mp[0]=1;//前缀和为0 的次数记为1
        int count=0,pre=0;
        for(auto& x:nums){
            pre+=x;
            if(mp.find(pre-k)!=mp.end()){//mp.end() 是 unordered_map 容器的一个成员函数，它返回一个指向容器末尾之后位置的迭代器，这个位置并不包含任何有效的元素，它只是一个标记，表示已经遍历完容器。
                count+=mp[pre-k];

            }
            mp[pre]++;
        }

        return count;
    }

};



//239. 滑动窗口最大值
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 获取数组的长度
        int n = nums.size();
        // 定义一个优先队列，存储元素的对 (元素值, 元素索引)
        // 这里定义了一个优先队列，存储的元素是 pair<int, int> 类型，优先队列会按照 pair 的第一个元素（也就是数组元素的值）进行降序排序，这样队列顶部（q.top()）的元素总是当前队列中值最大的元素。
        priority_queue<pair<int, int>> q;
        // 初始化优先队列，将前 k 个元素及其索引加入队列
        for (int i = 0; i < k; ++i) {
            // emplace 用于在队列中直接构造元素，避免不必要的拷贝
            q.emplace(nums[i], i);
        }
        // 初始化结果数组，将第一个滑动窗口的最大值加入结果数组
        vector<int> ans = {q.top().first};
        // 从第 k 个元素开始，依次移动滑动窗口
        for (int i = k; i < n; ++i) {
            // 将当前元素及其索引加入优先队列
            q.emplace(nums[i], i);
            // 当队列顶部元素的索引不在当前滑动窗口内时，移除队列顶部元素
            while (q.top().second <= i - k) {
                q.pop();
            }
            // 将当前滑动窗口的最大值加入结果数组
            ans.push_back(q.top().first);
        }
        // 返回结果数组
        return ans;
    }
};


// 76. 最小覆盖子串
class Solution {
     bool is_covered(int cnt_s[],int cnt_t[]){
        for(int i='A';i<='Z';i++){
            if(cnt_s[i]<cnt_t[i]){
                return false;
            }
        }
        for(int i='a';i<='z';i++){
            if(cnt_s[i]<cnt_t[i]){
                return false;
            }
        }
        return true;
     }
public:
    string minWindow(string s, string t) {
       int m=s.length();
       int ans_left=-1,ans_right=m;
       int cnt_s[128]{};//s字串字母出现的次数
       int cnt_t[128]{};//t中字母出现的次数

       for(char c:t){
        cnt_t[c]++;
       }

       int left=0;
       for(int right=0;right<m;right++){//移动子串右端点

            cnt_s[s[right]]++;
            while(is_covered(cnt_s,cnt_t)){//涵盖
                if(right-left<ans_right-ans_left){//找更短的子串
                    ans_left=left;
                    ans_right=right;
                }
                cnt_s[s[left]]--;//左端点字母移出子串
                left++;
            }

       }
       return ans_left<0 ? "" :s.substr(ans_left,ans_right-ans_left+1);
       //调用了 std::string 类的 substr 方法，该方法用于从字符串 s 中提取子串
       //ans_left 是子串的起始位置
       //ans_right - ans_left + 1 是子串的长度，ans_right 是最小覆盖子串的右端点，通过 ans_right - ans_left + 1 可以计算出这个子串包含的字符数量。
    }
};

